The invention relates to processing polygon strips, such as triangle strips, for example.
There are many ways for a computer system to represent three-dimensional (3-D) objects. For example, the computer system may use polygon meshes to represent the surfaces of the 3-D objects. One type of polygon mesh may include at least one triangle strip 8 (see FIG. 1) that is a collection of connected triangles 12 that are organized in a manner to minimize the number of vertices 9 that are used to describe the triangles 12. More particularly, a triangle may be described by three vertices, and thus, n triangles may be described by n*3 vertices. However, for the triangle strip 8, each triangle 12 shares a common edge with another triangle 12, an arrangement that permits n triangles to be described by n+2 vertices. In this manner, the triangle strip 8 (having sixteen triangles 12) may be described by the following vertex list (having 18 vertices): EQU {9a, 9b, 9c, 9d, 9e, 9f, 9g, 9h, 9i, 9j, 9k, 9l, 9m, 9n, 9o, 9p 9q, 9r}
The triangle strip 8 may have a winding order (i.e., the triangle strip 8 may be "ordered"), a designation that implies that the vertices of each triangle 12 appear in a sequence (in the vertex list) that indicates the direction of the surface normal of the triangle 12. In this manner, the triangle strip 8 typically is not planar (as depicted in FIG. 1 for purposes of simplicity), but rather, the triangle strip 8 may follow a non-planar path in 3-D space. As an example, a surface of a particular triangle 12 may form part of an object's exterior surface and as a result, may have a surface normal that points in a direction away from the exterior surface. Thus, the order in which the vertices associated with a particular triangle 12 appear in the vertex list may govern which surface of the triangle 12 forms part of the object's exterior surface.
More particularly, when the computer system processes the above-described vertex list to render an image of the triangle strip 8, the computer system may initially draw a triangle 12a that has the vertices 9a, 9b and 9c and is bounded by a conceptual piecewise parametric curve 5 that extends through the vertices 9a, 9b, and 9c. The direction (clockwise or counterclockwise) of a parametric curve (such as the parametric curve 5) may be determined by the order in which the vertices are connected to form the curve, and the direction of the curve may govern which surface of the triangle is an exterior surface, as described below.
The winding order of the triangle strip 8 effectively alternates the applications of the right hand and left hand rules to the parametric curves (that bound the triangles 12) to determine the directions of the surface normals. For example, to form the leftmost triangle 12a of the strip 8, the computer system may connect the first three vertices {9a,9b,9c} together in the order (a left-to-right order, for example) that is defined by the sequence in which the vertices appear in the vertex list described above: vertex 9a to vertex 9b to vertex 9c to vertex 9a (to close the curve). Thus, the resultant parametric curve 5 has a counterclockwise orientation (as depicted in FIG. 1). Applying the right hand rule, the surface normal of the triangle 12a points out of the page, for example. It is noted that if the leftmost triangle is alternatively defined by the vertex sublist {9a,9c,9b}, then the resultant parametric curve (given the drawing order described above) has a clockwise (instead of a counterclockwise) orientation, and thus, applying the right hand rule, the surface normal of the triangle points into the page.
As another example, the next triangle 12b to the right of the triangle 12a is defined by one additional vertice 9d that, when combined with the vertex sublist {9b,9c} (i.e., the two prior vertices of the vertex list), causes the computer system to form a conceptual parametric curve 6 in the following manner: vertex 9b to vertex 9c to vertex. 9d to vertex 9b. Thus, the parametric curve 6 has a clockwise orientation, and the winding order ensures that the left hand rule applies (because of the alternating applications of the left hand and right hand rules) to determine the direction of the surface normal. Thus, applying the left hand rule to the parametric curve 6, the surface normal of the triangle 12b points out of the page.
Three dimensional objects may be defined in an object space by a mesh of multiple triangle strips that are oriented in various directions, and the computer system may process the vertex lists that define the triangle strips to transform the vertices into a two-dimensional (2-D) screen space for display. As an example, the computer system may represent a portion of an exterior surface of a sphere 9 (in an object space) by a triangle strip 8a, as depicted in FIG. 2. When transformed into screen coordinates as seen through a viewing window 7, a portion 8aa of the strip 8a may be visible, and another portion 8ab of the strip 8a may be invisible. Unfortunately, the computer system may consume a considerable amount of time processing triangles, such as the triangles that form the portion 8ab, that do not ultimately appear in the 2-D screen space. These additional computations (e.g., transformations of the vertices from one coordinate space to another coordinate space), in turn, may degrade performance of the computer system.
Thus, there is a continuing need for an arrangement that reduces the number of polygons that are processed by a computer system but do not appear in the final image that is rendered by the computer system.